package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;
import com.lun.util.Pair;

public class SmallestSubtreeWithAllTheDeepestNodes {
	
	//方法一：自己写的，用后序遍历模式
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
    	Object[] result = subtreeWithAllDeepest(root, 0);
    	return result != null ? (TreeNode)result[0] : null;
    }
    
    private Object[] subtreeWithAllDeepest(TreeNode node, int depth) {
    	if(node == null) return null;
    	
    	depth++;
    	
    	Object[] leftResult = subtreeWithAllDeepest(node.left, depth);
    	Object[] rightResult = subtreeWithAllDeepest(node.right, depth);
    	
    	if(leftResult == null && rightResult == null) {//叶子节点
    		return new Object[] {node, depth};
    	}else if(leftResult != null && rightResult == null){
    		return leftResult;
    	}else if(leftResult == null && rightResult != null) {
    		return rightResult;
    	}else {
    		int leftDepth = (int)leftResult[1];
    		int rightDepth = (int)rightResult[1];
    		
    		if(leftDepth > rightDepth) {
    			return leftResult; 
    		}else if(leftDepth < rightDepth) {
    			return rightResult;
    		}else {
    			leftResult[0] = node;
    			return leftResult;
    		}
    	}
    }
    
    //方法一：别人写的写的，用后序遍历模式
    public TreeNode subtreeWithAllDeepest2(TreeNode root) {
        return deep(root).getSecond();
    }

    public Pair<Integer, TreeNode> deep(TreeNode root) {
        if (root == null) return new Pair<>(0, null);
        Pair<Integer, TreeNode> l = deep(root.left), r = deep(root.right);

        int d1 = l.getFirst(), d2 = r.getFirst();
        return new Pair<>(Math.max(d1, d2) + 1, d1 == d2 ? root : d1 > d2 ? l.getSecond() : r.getSecond());
    }
    
    
}
